|
In combinatorics, a Davenport–Schinzel sequence is a sequence of symbols in which the number of times any two symbols may appear in alternation is limited. The maximum possible length of a Davenport–Schinzel sequence is bounded by the number of its distinct symbols multiplied by a small but nonconstant factor that depends on the number of alternations that are allowed. Davenport–Schinzel sequences were first defined in 1965 by Harold Davenport and Andrzej Schinzel to analyze linear differential equations. Following these sequences and their length bounds have also become a standard tool in discrete geometry and in the analysis of geometric algorithms.〔, pp. x and 2.〕 ==Definition== A finite sequence ''U'' = ''u''1, ''u''2, ''u''3, is said to be a Davenport–Schinzel sequence of order ''s'' if it satisfies the following two properties: #No two consecutive values in the sequence are equal to each other. #If ''x'' and ''y'' are two distinct values occurring in the sequence, then the sequence does not contain a subsequence ... ''x'', ... ''y'', ..., ''x'', ..., ''y'', ... consisting of ''s'' + 2 values alternating between ''x'' and ''y''. For instance, the sequence :1, 2, 1, 3, 1, 3, 2, 4, 5, 4, 5, 2, 3 is a Davenport–Schinzel sequence of order 3: it contains alternating subsequences of length four, such as ...1, ... 2, ... 1, ... 2, ... (which appears in four different ways as a subsequence of the whole sequence) but it does not contain any alternating subsequences of length five. If a Davenport–Schinzel sequence of order ''s'' includes ''n'' distinct values, it is called an (''n'',''s'') Davenport–Schinzel sequence, or a ''DS''(''n'',''s'')-sequence.〔See , p. 1, for this notation.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Davenport–Schinzel sequence」の詳細全文を読む スポンサード リンク
|